package subject_set.offer100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/10/14 22:25
 **/
public class Offer22 {
    class Solution {
        public ListNode getKthFromEnd(ListNode head, int k) {
            Deque<ListNode> stack = new LinkedList<>();
            while(head != null) {
                stack.push(head);
                head = head.next;
            }
            while(k-- > 1) {
                stack.poll();
            }
            return stack.poll();
        }
    }
    class Solution2 {
        public ListNode getKthFromEnd(ListNode head, int k) {
            ListNode node1 = head;
            ListNode node2 = head;
            while(k-- > 0) node1 = node1.next;
            while(node1 != null){
                node1 = node1.next;
                node2 = node2.next;
            }
            return node2;
        }
    }
}